/**
 * 哈希表的概念
 *    哈希化:将大数字转化成数组范围内下标的过程
 *    哈希函数:我们通常会将单词转成大数字 把大数字进行哈希化的代码实现放在一个函数中 就称为哈希函数
 *    哈希表:对最终数据插入的数组进行整个结构的封装 得到的就是哈希表
 */
// 解决哈希冲突的方法:链地址法 开放地址法
// 装填因子 表示当前哈希表中已经包含的数据项和整个哈希表长度的比值
/**
 * 哈希函数
 * @param {*} string 进行哈希化的字符串
 * @param {*} limit 
 * @returns 
 */
function hashFn (string, limit = 7) {
  // 自己采用的一个质数（无强制要求，质数即可）
  const PRIME = 31;

  // 1、定义存储 hashCode 的变量
  let hashCode = 0;

  // 2、使用霍纳法则（秦九韶算法），计算 hashCode 的值
  for (let item of string) {
    hashCode = PRIME * hashCode + item.charCodeAt();
  }

  // 3、对 hashCode 取余，并返回
  return hashCode % limit;
}
// 判断一个数是不是质数
function isPrime (number) {
  if (number <= 1 || number === 4) return false
  const temp = Math.ceil(Math.sqrt(number))
  for (let i = 2; i < temp; i++) {
    if (number % i === 0) {
      return false
    }
  }
  return true
}
// 创建hash类
class HashTable {
  constructor () {
    // storage最终形式[[k,v],[k,v],[k,v],[[k,v]]]
    this.storage = [] //哈希表存储数据的变量
    this.limit = 7  //哈希表的长度
    this.count = 0  // 当前存放元素的个数

    this.loadFactor = 0.75 // 装填因子
    this.minLoadFactor = 0.25 // 最小装填因子
  }
  // 获取最邻近的质数
  getPrime (number) {
    while (!isPrime(number)) {
      number++
    }
    return number
  }
  // 哈希表的插入与修改
  put (key, value) {
    // 1、根据 key 获取要映射到 storage 里面的 index（通过哈希函数获取）
    const index = hashFn(key, this.limit);

    // 2、根据 index 取出对应的 bucket
    let bucket = this.storage[index];

    // 3、判断是否存在 bucket
    if (bucket === undefined) {
      bucket = [];  // 不存在则创建
      this.storage[index] = bucket;
    }

    // 4、判断是插入数据操作还是修改数据操作
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i]; // tuple 的格式：[key, value]
      if (tuple[0] === key) { // 如果 key 相等，则修改数据
        tuple[1] = value;
        return; // 修改完 tuple 里数据，return 终止，不再往下执行。
      }
    }

    // 5、bucket 新增数据
    bucket.push([key, value]); // bucket 存储元组 tuple，格式为 [key, value]
    this.count++;

    // 判断哈希表是否要扩容，若装填因子 > 0.75，则扩容
    if (this.count / this.limit > this.loadFactor) {
      this.resize(this.getPrime(this.limit * 2));
    }
  }
  /**
   * 采用链地址法 装填因子可以大于1 所以可以无线地插入新的数据 随着数据量地增多 每个index 对应地bucket 数组 链表 就会越来越长 造成哈希表效率地降低
   * 哈希表扩容/压缩 
   * @param {*} newLimit 哈希表的新长度
   */
  resize (newLimit) {
    // 保存现有的storage内容
    let oldStorage = this.storage
    //重置所有的属性
    this.storage = []
    this.count = 0
    this.limit = newLimit
    for (const bucket of oldStorage) {
      if (bucket) {
        for (const b of bucket) {
          this.put(b[0], b[1]);
        }
      }

    }
  }
  /**
   * 获取某个哈希表的值
   * @param {*} key 
   */
  get (key) {
    //1.通过hash函数获取key在storage中的索引
    const index = hashFn(key, this.limit);
    // 取出哈希表当前索引存储的bucket
    let bucket = this.storage[index]
    if (bucket === undefined) return null
    for (let i = 0, len = bucket.length; i < len; i++) {
      if (key === bucket[i][0]) {
        return bucket[i][1]
      }
    }
    return null
  }
  /**
   * 删除hash表中的某个值
   * @param {*} key 
   */
  remove (key) {
    //1.通过hash函数获取key在storage中的索引
    const index = hashFn(key, this.limit);
    // 取出哈希表当前索引存储的bucket
    let bucket = this.storage[index]
    if (bucket === undefined) return null
    // 遍历 bucket，找到对应位置的 tuple，将其删除
    for (let i = 0, len = bucket.length; i < len; i++) {
      const tuple = bucket[i];
      if (tuple[0] === key) {
        bucket.splice(i, 1); // 删除对应位置的数组项
        this.count--;

        // 根据装填因子的大小，判断是否要进行哈希表压缩
        if (this.limit > 7 && this.count / this.limit < this.minLoadFactor) {
          this.resize(this.getPrime(Math.floor(this.limit / 2)));
        }

        return tuple;
      }

    }

  }
  /**
   * 
   * @returns 判断hash表是否为空
   */
  isEmpty () {
    return this.count == 0
  }
  /**
   * 返回哈希表的长度
   * @returns 
   */
  size () {
    return this.count
  }
}
// console.log(hashFn('name'));
// console.log(hashFn('age'));
// console.log(hashFn('height'));
const hashTable = new HashTable()
hashTable.put('name', 'Hyun')
hashTable.put('age', 18)
hashTable.put('height', 183)
hashTable.put('email', 'i@xpoet.cn');
hashTable.put('address', 'china');
// console.log(hashTable);
// [
//   <1 empty item>,
//   [ [ 'name', 'Hyun' ] ],
//   [ [ 'age', 18 ], [ 'email', 'i@xpoet.cn' ] ],
//   <1 empty item>,
//   [ [ 'height', 183 ] ],
//   [ [ 'address', 'china' ] ]
// ]
hashTable.put('address2', 'china2');
// console.log(hashTable);
// console.log(hashTable.storage);
hashTable.remove('address')
console.log(hashTable);
console.log(hashTable.storage);
console.log(hashTable.get('name'));
console.log(hashTable.size());
console.log(hashTable.isEmpty());
// // 工具函数
// function isUndef (v) {
//   return v === void 0
// }